package com.algorithm.list_node;

import com.dataconsruct.ListNode;
import org.junit.Test;

/**
 * 合并两个有序链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * @author gatts, 2025/9/22 19:51
 */
public class MergeTwoListsTest {

    @Test
    public void test() {
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2, new ListNode(4));

        ListNode node2 = new ListNode(1);
        node2.next = new ListNode(3, new ListNode(4));

        ListNode result = mergeTwoLists(node1, node2);
        System.out.println(result);
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        // 虚拟头结点
        ListNode dummyHead = new ListNode(-1);
        // 两个链表的当前指针
        ListNode cur1 = a, cur2 = b;
        // head用来返回最终结果，tail随着两个指针移动，不断把新的节点添加到尾部
        ListNode tail = dummyHead;

        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                tail.next = cur1;
                cur1 = cur1.next;
            }
            else {
                tail.next = cur2;
                cur2 = cur2.next;
            }
            tail = tail.next;
        }

        tail.next = cur1 == null ? cur2 : cur1;
        return dummyHead.next;
    }

}
